一文带你了解 TreeMap ,LinkedHashMap 的主要特点
最近写了这个 HashMap , 这篇就简单讲讲 TreeMap ,LinkedHashMap 的特点~
内功加一 !😝
必备知识点
一. Comparable
, Comparator
这两个有什么不同?
可以看到一个是 java.lang 包的,一个是 util 包的。
代码如下,很明显, Comparable
属于 内部比较器, 而 Comparator
属于 外部比较器 。
外部比较器的好处 是我们可以有很多这种比较器,可以按排序的要求去选择 ,便于解耦。
而内部比较器也比较简单,只要实现了该 Comparable
接口就可以进行比较了。
class B implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
}
class C implements Comparable<Integer>{
private final int num;
public C(int num){
this.num=num;
}
@Override
public int compareTo(Integer o) {
return this.num-o;
}
}
接着让我们来看看这个 TreeMap~ 😝
TreeMap 特点
1. 有序
2. key 不能为 null
解析:
如图所示 TreeMap
实现了这个 SrotedMap
接口,SortMap
接口中定义了这个 Comparator
外部比较器。
我们可以在创建 TreeMap 时传入~ ,不传入的话时没有这个外部比较器 Comparator
的。
那么问题来啦!为什么 key 不能是null 呢?
请看下图分析~😋
序号1,这里表示当你第一次put 时,会进入 compare
方法,源码如下:
/**
* Compares two keys using the correct comparison method for this TreeMap.
*/
@SuppressWarnings("unchecked")
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
可以发现如果你木有定义这个 外部比较器的话,它会转化为这个 内部比较器 Comparable
进行比较 。
可以看到当你传进来的 key 为 null 时,即 k1 为 null,此时调用 compareTo 方法就会抛出 NullPointerException
。效果等于 null.compareTo(k2)
。
当你自定义了 外部比较器的 话, 还得看看这个 比较器中 compare 方法的写法,稍不注意也会抛出空指针异常
如果在这里有加入 非空判断的话,是不会抛出空指针异常的~ (序号2 可以参考这里)
class B implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
if (o1==null||o2==null){
return -1;
}
return o1-o2;
}
}
图中序号3,可以看到直接抛出空指针异常啦~
所以,真正的答案应该是
当你自定义了 外部比较器 Comparator 时,你可以允许 key 为null ,不过一般不建议~ 。😝
当你没有自定义 外部比较器 Comparator 时, TreeMap 会为 key 使用 内部比较器 Comparable ,此时不允许 key 为 null 😝
总结:
TreeMap 的特点是有序,默认情况下会根据 key 进行自然排序,此时 key 不能为 null ,而 自定义 外部比较器 Comparator 时 ,是可以允许 key 为 null 的
嘿嘿 趁热打铁,让我们把 目光 移动到另外一个和 顺序有关的 Map
—— LinkedHashMap
LinkedHashMap
看看它滴类图~ 可以看到它 继承了 HashMap 。
可以看到这里在说它是在HashMap的基础上维护了一个双向链表,后面是在说它的作用是保证 插入的有序
这一部分就不展开啦,主要重写了 newNode 等方法,去 维护这个双链表~
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
总结
LinkedHashMap
的 特点是 双向链表,插入有序
而且遍历时也是直接遍历双向链表的,插入时间复杂度为O(1),查找时间复杂度O(n)
完结~ 撒花★,°:.☆( ̄▽ ̄)/$:.°★ 。
👉 下一篇再写写这最后一个 ConcurrentHashMap ,然后是 锁 ~ 部分的知识点 ! !!
创作不易, 点个赞,关注下 交个朋友可好! xiexie~ 😝
谢谢可爱又帅气的大佬们的观看!祝您 天天开心!😄
感谢您的关注!您的每个关注,都是博主 肝肝肝的动力 😝
点个“在看”表示朕
面试, HashMap,看?
你听说过 Fail-fast 机制吗?程序的浪漫?
一文带你看遍单例模式的八个例子,面试再也不怕被问了
摸鱼小技巧之IDEA调试篇一